package com.sicheng.lc.周赛.分类.dp.rmq;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/22 10:57
 */
@SuppressWarnings("all")
public class 巫师的总力量和 {
    /**
     * https://leetcode.cn/contest/weekly-contest-294/problems/sum-of-total-strength-of-wizards/
     * 作为国王的统治者，你有一支巫师军队听你指挥。
     * <p>
     * 给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：
     * <p>
     * 巫师中 最弱 的能力值。
     * 组中所有巫师的个人力量值 之和 。
     * 请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。
     * <p>
     * 子数组 是一个数组里 非空 连续子序列。
     */

    int n;
    int[] a;
    int[][] dp;

    //预处理O（nlogn）
    void rmq() {
        for (int i = 1; i <= n; i++) {
            dp[i][0] = a[i];
        }

        for (int j = 1; (1 << j) <= n; j++) {
            //从i开始 右端点(i,i+2^j-1)
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                dp[i][j] = Math.min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    //查询 O（1）
    int query(int l, int r) {
        int k = (int) (Math.log(r - l + 1) / Math.log(2));
        return Math.min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }


    public int totalStrength(int[] strength) {
        int mod = (int) (1e9 + 7);
        dp = new int[strength.length + 1][strength.length + 1];
        n = strength.length;
        a = new int[n + 1];
        System.arraycopy(strength, 0, a, 1, n);
        rmq();
        for (int i = 1; i < a.length; i++) {
            a[i] = (a[i] + a[i - 1]) % mod;
        }
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                sum = (sum + (long) (a[j] - a[i - 1]) * query(i, j) % mod) % mod;
            }
        }
        return (int) sum;
    }

    public static void main(String[] args) {
        巫师的总力量和 rmq = new 巫师的总力量和();
        int[] strength = {1, 3, 1, 2};
        System.out.println(rmq.totalStrength(strength));
    }
}
